/****************************************************
  @title: 数据结构实验
  @name: <实验9-1b> 斐波那契查找 
  @object:
      [实验目的]
          实现斐波那契查找算法 
      [实验提示]
          1. 实现斐波那契查找算法
          2. 改写算法，打印出查找过程
          3. 画出表长为20时的查找判定树 
  @include:
  @usage:
      请查看"TO-DO列表",根据要求完成代码
  @copyright: BTC 2004, Zhuang Bo
  @author: Zhuang Bo
  @date: 2004
  @description:
*****************************************************/

#include <stdio.h>
#include <stdlib.h> //for system()

#define ElemType int

//斐波那契查找
int FibSearch(ElemType a[], int n, ElemType e);
//斐波那契查找,同时打印查找过程 
int FibSearchView(ElemType a[], int n, ElemType e);
//打印数组内容
void PrintArray(int a[],int n);


int main()
{
    const int N = 20;
    ElemType a[N+1]={0,
        1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
    };
    ElemType x;
    int i;
    
    //查找表中的数据
    printf("a[]=");
    PrintArray(a,N);
    
    //进行斐波那契查找
    printf("输入待查找的数据:");
    scanf("%d", &x); 
    
    if( (i=FibSearch(a,N,x))>0 )
        printf("找到 a[%d]=%d\n", i, a[i]);
    else
        printf("没找到\n");
    
    //查找过程
    printf("\n查找过程\n"); 
    FibSearchView(a,N,x);
    printf("\n查找结束\n"); 
    
    system("PAUSE");	
    return 0;
}

//计算斐波那契数列第n项
int fib(int n) 
{
    if(n==0||n==1)  return n;
    int a=0,b=1,c;
    for(int i=2; i<=n; i++)
        c=a+b, a=b, b=c;
    return c;
}

//在a[1..n]中进行斐波那契查找
//  找到x，返回下标；否则返回0 
int FibSearch(ElemType a[], int n, ElemType x)
{
    //-------------------------------------
    // TODO (#1#): 斐波那契查找
    return 0;
    //-------------------------------------
}


//斐波那契查找,同时打印查找过程 
int FibSearchView(ElemType a[], int n, ElemType x)
{
    //-------------------------------------
    // TODO (#1#): 在查找的同时打印出比较结果 
    return 0;
    //-------------------------------------
}

//打印数组数据a[1..n]
void PrintArray(int a[],int n)
{
	int i;
	printf("{ ");
	for(i=1; i<=n; i++)
		printf("%d ",a[i]);
	printf("}\n");
}

